This volume contains the proceedings of ICTAC 2004, the 1st International Colloquium on Theoretical Aspects of Computing, which was held in Guiyang, China on 20-24 September 2004. ICTAC was founded by the International Institute for Software Technology of the United Nations University (UNU-IIST). Its aim is to bring together pr- titioners and researchers from academia, industry, and government to present research results, and exchange experience, ideas, and solutions for their pr- lems in theoretical aspects of computing. The geographic focus of the ICTAC events is on developing countries to help to strengthen them in their research, teaching, and development in computer science and engineering, to encourage research cooperation among developing countries, and to improve the links - tween developing countries and industrial countries. The Program Committee of ICTAC 2004 received 111 submissions from over 30 countries and regions. Each paper was reviewed, mostly by at least three r- ereesworkinginrelevant?elds, butbytwoinafewcases.Borderlinepaperswere further discussed during an online meeting of the Program Committee. Thir- fourpaperswereacceptedbasedonoriginality, technicalsoundness, presentation andrelevancetosoftwareengineeringandformalmethods.Wesincerelythankall the authors who submitted their work for consideration. We thank the Program Committee members and the other referees for their great e?ort and professional workinthereviewingandselectingprocess.Theirnamesarelistedonthefoll- ing pages. In addition to the contributed papers, the proceedings also includes contributions from the invited speakers: Jos´ e Luiz Fiadeiro, He Jifeng, Huimin Lin and Rustan Leino.