富爾頓斷定最好的辦法是在“循環鏈”上安裝扁平木板狀的槳，用一個滑輪帶動漿在船頭和船尾運動，由此產生的能量傳送到氣缸各側的曲軸輪。這很像菲奇最初的發明成果。但是當巴洛在信上說，一個名為迪斯布朗斯（Desblancs）的法國發明家正在巴黎展示一種類似裝置的時候，富爾頓決定運用一個像研磨廠用的水車那樣的裝置來解決。此外，他又一次對獨創性問題未做太多考慮。“雖然輪子的應用不是什麼新鮮事，”他告訴利文斯頓，“然而，要是我把它們按照這樣一種方式結合起來應用，那麼蒸汽機會有更大的能量以同樣的運動方式推動輪船前進，這個道理就好像腳踏實地做買賣一樣簡單，這種應用相同原理的裝置結合將會勝過所有到目前為止出現的一切發明，而它實際上就是一種新的發明。”
在返回巴黎的途中，富爾頓同利文斯頓進行了一次艱難的商談，最終於1802年10月10日簽字確定了合作關係。這個值得紀念的協議提出，富爾頓負責在紐約建造一艘吃水8英尺、長120英尺的輪船，可以搭載至少60名乘客到奧爾巴尼。利文斯頓要為這艘船的製造提供現金，並利用他的政治影響力保護他們在紐約的壟斷地位，富爾頓負責設計和管理，他們將平分所得利潤。如果該項目失敗了，富爾頓必須歸還利文斯頓的一半投資。
1803年，兩個合夥人同意在法國造船體，並在塞納河試航。利文斯頓從英國購買蒸汽機的努力沒有成功，因此富爾頓冒險在巴黎租賃了一台蒸汽機和鍋爐，但不久鍋爐就爆炸了，他們隻能另外租了一台。1803年5月，他們在塞納河船塢將鍋爐安裝到一艘75英尺長的船上。就在即將進行嚐試的那個讓人心潮澎湃的時刻到來前夕，富爾頓的房門傳來一陣巨大的敲擊聲。“一個報信者的驚叫聲把我喚醒了：“噢，先生，輪船已經成了碎片，沉下去了。”我感到了一種前所未有的強烈失望。”
也許，像一些報紙上說過的那樣，這是妒忌的船夫們的蓄意破壞；也或許是笨重的低壓蒸汽機超過了船體的承重能力。發狂的富爾頓冒雨衝進了河裏。在接下來的日子裏，他沒日沒夜、廢寢忘食地工作，為了修複從河底打撈上來的蒸汽機，他把自己累得筋疲力盡。
到1803年8月9日這天，他們做好了再次試航的準備。一家法國報紙報道：“傍晚6點，僅在3個人的幫助下，他便利用另外兩艘船的牽引啟動了修好的輪船。隨後1個半小時內，奇怪的一幕出現了：他移開舵輪，使輪船看上去像運貨的馬車，這些舵輪裝配了劃槳和扁平的木板，而且靠火力蒸汽機驅動。”富爾頓的蒸汽船沿著塞納河以大約每小時3英裏的速度行駛。《辯論日報》（Journal des debats）說它是“完全失敗的輝煌”。富爾頓期待的速度是每小時16英裏，不過3英裏的時速是邁向成功的開始。這是對傳統觀點的挑戰，當時費城著名建築師和設計師本傑明·拉特羅布（Benjamin Latrobe）提出了蒸汽航海根本不可行這一說法。然而現在，不尋常的事情發生了，而且還會出現可預見的成功。
然而這兩個合作夥伴沒有把注意力放在蒸汽船上。利文斯頓同拿破侖的談判獲得了成功。他抓住機會，以每英畝3美分不到的價格為美國購買了5.65億英畝的土地。他同詹姆斯·門羅一起經過談判從法國手中所買到的路易斯安那使美國的領土麵積增加了一倍。帶著成功的喜悅，利文斯頓回到他在紐約的莊園飼養美利諾綿羊去了。而他的夥伴富爾頓，在1804年5月則與其方向相反，到倫敦去了，他要在那裏待兩年半。