Po nieudanej próbie zamieszkania w Paryżu i wydaleniu go przez policję z Francji jako emisariusz Centralizacji TDP został wysłany na Ukrainę. Przez Marsylię, Stambuł i Jassy przedostał się do przygranicznego regionu Ukrainy, Pobereża, a następnie do Kijowa, gdzie zawiązał tajny komitet. Jednak niebawem policja wpadła na jego trop i spiskowców bądź rozstrzelano bądź zesłano na Sybir. Samemu Miłkowskiemu udało się uciec do Mołdawii.
W latach 1851–1858 był agentem Komitetu Centralnego Demokracji Europejskiej na Bałkanach. Początkowo działał na terenie Rumunii, następnie od 1855 przebywał w Stambule. W tym czasie utrzymywał się z pracy na rzecz jednej z francuskich firm handlowych, a także prowadząc jadłodajnię w Stambule. Podczas wojny krymskiej próbował wraz z gen. Józefem Wysockim sformować legion polski przy boku Turcji. W latach 1858–1860 członek Centralizacji TDP. W tym czasie przebywał w Paryżu i Londynie, gdzie współpracował z „Przeglądem Rzeczy Polskich” oraz nawiązał stosunki z Aleksandrem Hercenem i Giuseppe Mazzinim. Uważał wówczas, że wobec odbudowy w Polsce życia politycznego emigracja nie powinna narzucać krajowi swego przywództwa.