The　tremendous　parallel　computing　ability　of　Cloud　computing　as　a　new　service　provisioning　paradigm　encourages　investigators　to　research　its　drawbacks　and　advantages　on　processing　large-scale　scientific　applications　such　as　workflows.　The　current　Cloud　market　is　composed　of　numerous　diverse　Cloud　providers　and　workflow　scheduling　is　one　of　the　biggest　challenges　on　Multi-Clouds.　However,　the　existing　works　fail　to　either　satisfy　the　Quality　of　Service　(QoS)　requirements　of　end　users　or　involve　some　fundamental　principles　of　Cloud　computing　such　as　pay-as-you-go　pricing　model　and　heterogeneous　computing　resources.　In　this　paper,　we　adapt　the　Partial　Critical　Paths　algorithm　(PCPA)　for　the　multi-cloud　environment　and　propose　a　scheduling　strategy　for　scientific　workflow,　called　Multi-Cloud　Partial　Critical　Paths　(MCPCP),　which　aims　to　minimize　the　execution　cost　of　workflow　while　satisfying　the　defined　deadline　constrain.　Our　approach　takes　into　account　the　essential　characteristics　on　Multi-Clouds　such　as　charge　per　time　interval,　various　instance　types　from　different　Cloud　providers　as　well　as　homogeneous　intra-bandwidth　vs.　Heterogeneous　inter-bandwidth.　Various　well-know　workflows　are　used　for　evaluating　our　strategy　and　the　experimental　results　show　that　the　proposed　approach　has　a　good　performance　on　Multi-Clouds.　©　2015　IEEE.