Wedle jednej z teorii wywodzili się oni od żyjącego w połowie XVI w. Pawła, dziedzica Sułkowa Borowego na Mazowszu. Kasper Niesiecki, autor słynnego „Herbarza Polski”, podaje z kolei, że poza okolicami Łęczycy zamieszkiwali Sułkowscy województwo podolskie, a ich przedstawicielem był żyjący na początku XVII w. Wacław Sułkowski, podczaszy bracławski.
Jedna z najczęściej powtarzanych, ale nieznajdująca potwierdzenia w źródłach, plotek związanych z rodem dotyczy twórcy jego potęgi Aleksandra Józefa Sułkowskiego (1695–1762), który rzekomo miał być naturalnym synem króla polskiego Augusta II Mocnego. Teza ta zdobyła przez lata taką popularność, że dziś uchodzi już niemal za fakt. Tymczasem według Dariusza Nawrota i Grzegorza Madeja, autorów poświęconej rodowi książki „Zapomniani książęta Sułkowscy w XVIII–XX w.”, kwestia rodziców Sułkowskiego, czyli Stanisława Sułkowskiego i Elżbiety z Wągrowskich „nie budzi żadnych wątpliwości”.
Początek spektakularnej karierze Aleksandra Józefa na dworze w Dreźnie dała nić przyjaźni, jaka zawiązała się między nim a królewiczem Fryderykiem Augustem II, synem elektora Saksonii i króla Polski. Za młodu Sułkowski towarzyszył następcy tronu podczas podróży na zachód Europy w latach 1711–19. Trafiwszy do Drezna, został przyjęty do tamtejszego Korpusu Paziów. Dla syna średniozamożnego szlachcica było to niemałe wyróżnienie, ponieważ do korpusu dopuszczano zwykle członków magnaterii. Z czasem Aleksander Józef zasłynął jako organizator wspaniałych polowań, które cieszyły się rangą wydarzeń towarzyskich wśród drezdeńskiej socjety. Śmierć Augusta II Mocnego otworzyła Polakowi drogę do wielkiej kariery. W latach 1733–38 pełnił on funkcję pierwszego ministra gabinetowego Saksonii, czyli drugiej po elektorze osoby w państwie.