W 1776 roku został wysłany do Kanady, aby wesprzeć amerykańską inwazję, gdzie objął dowództwo nad wycofującymi się siłami po śmierci generała Johna Thomasa.
W sierpniu 1776 roku awansowano go na stopień generała dywizji. Wkrótce potem, w czasie bitwy na Long Island, dostał się do niewoli brytyjskiej. Został wymieniony w grudniu i dołączył do armii George’a Washingtona, aby wziąć udział w bitwie pod Trenton, gdzie dowodzona przez niego kolumna odegrała kluczową rolę w odcięciu drogi ucieczki heskim najemnikom. Sullivan brał również udział w bitwie pod Brandywine i bitwie pod Germantown (1777).
Ekspedycja Sullivana Najbardziej znaną, a zarazem kontrowersyjną, operacją dowodzoną przez Sullivana była ekspedycja z 1779 roku. W odpowiedzi na ataki Irokezów (sprzymierzonych z Brytyjczykami) na osady w dolinie Mohawk, Washington zlecił Sullivanowi przeprowadzenie kampanii karnej. Poprowadził on armię liczącą blisko 4000 żołnierzy na terytorium Irokezów w zachodniej części stanu Nowy Jork.