Písať začal už počas štúdií na učiteľskej akadémii, prvé básne a prózy uverejnil v časopisoch Tvorba, Mladá tvorba a Slovenské pohľady. Knižne debutoval v r. 1958 básnickou zbierkou Letokruh srdca. Citovo silne zafarbená prírodná a predovšetkým ľúbostná lyrika, cez ktorú reflektoval životné peripetie počas vojny, prvé lásky a trpké osobné skúsenosti z 50. rokov, sa nestretla s priaznivým prijatím kritiky, a Andrej Chudoba sa do širšieho povedomia dostal až ako prozaik. Už prozaický debut – dvojnovela Kde pijú dúhy – nesie pečať, na základe ktorej ho kritika označila za pokračovateľa tradície lyrizovanej prózy. Významnú úlohu zohráva poeticky i mýtotvorne vnímaná prírodná scenéria (oblasť Tekova na juhu Slovenska), s ktorou sú spojené živelné postavy. Dôraz sa kladie na ich intenzívne prežívanie medziľudských vzťahov, často s výraznou erotickou dimenziou. Ako naznačuje už názov, Chudobove postavy sa zbavujú pocitov krivdy a frustrácie najmä cez ľúbostné vzťahy. Jeho osobitným sujetovým riešením bolo, že postavy vzdorujú akoby samy zo seba, z vitálneho vnútra. Z neho sa rodí nielen ich erotizmus a iracionalita, ale aj „prisanie“ sa na život všetkými zmyslami. Práve úsilie o prekonávanie tragiky života z vlastného vnútra zostane trvalou súčasťou Chudobovej predstavy človeka a literatúry. V trende prekonávať traumy pokračoval aj v knihách noviel Pustý dvor a Miesto pre dvoch. Temné miesta v minulosti postáv však využíva len na fabulačné stajomnenie a zatraktívnenie. Nie je to inak ani v nasledujúcej novele Leto s pehavou pannou o príležitostnom vzplanutí vekovo neprimeraných partnerov. Jej komorný dej je obohatený o detektívnu zápletku s výraznou psychologizujúcou tendenciou a s tragickým rozuzlením. Dezilúziou, rozchodom a smrťou sa končí väčšina poviedok v zbierke Zbohom, Cyrano, rozprávaných v prvej osobe bez patetizovania, len ako zvláštne príbehy všedných dní. Prvky detektívnej literatúry sa vyskytujú aj v románoch Nákaza a Stopárka. Ale autor, verný sebe, sa napr. aj v románe Nákaza viac ako na priebeh odstraňovania následkov havárie na živočíšnej farme sústredil na demonštrovanie nespútateľnosti života aj v podmienkach karantény. Tak sa čitateľ dozvie viac o „sedliackom dekamerone“ ako o boji s haváriou. Do školského prostredia situoval autobiograficky ladený román z povojnového obdobia Zázrak na konci sveta, k rozličným podobám lásky sa vrátil v knihe poviedok Hlinené husle a krátkych noviel Konečne bude mier. V románe Krásne poškodená slečna nadobúda ústredná téma Chudobovej tvorby, vzťah medzi mužom a ženou, povahu mýtu. Detskému čitateľovi adresoval prerozprávané povesti z oblasti Tekova a Hontu Sedemdesiatsedem povestí spod Slovenskej brány. S významnými slovenskými fotografmi spolupracoval na vydaní obrazových publikácií Rodná zem (s K. Benickým), Čaro zimy (s O. Neherom), Od Tekova vietor veje... (s. M. Hlôškom), Veľký spev (s K. Benickým), Krajina môjho srdca (s V. Bártom), ktoré doplnil lyrickými veršami s tematickou domova. Okrem toho je autorom filmových scenárov (Most na tú stranu, Chlapec do náručia), televíznych hier (Smäd, Deň bez anjela, Konečne bude mier, Zina) a rozhlasových adaptácií (Syn človeka, Nákaza, Zvony z Asiagu, Zbohom, Cyrano).
