Under sin tid som flygingenjör i Prag 1961–67 arbetade Koudelka som frilansfotograf, främst inom teatervärlden. Han blev först känd för sina realistiskt starka bilder av romer i Tjeckoslovakien och Rumänien, skildrade med inlevelse och närhet i djärvt komponerade svartvita bilder med mustig svärta.