The baobab (Adansonia digitata L.) is a remarkable key tree species with different uses in many African countries. International interest in the species has intensified in recent years. Despite the wide distribution of the baobab in many African regions, the tree has been reported to be absent in Uganda. In 2015 and 2016, research trips in the Central, Western, Eastern and Northern Regions of Uganda were conducted to screen the cultivated and natural flora for baobabs. As a result, four vigorous baobab trees aged 9 and 22 years were identified in two gardens in the Iganga and Soroti Districts in the Eastern Region of Uganda. The origins of the planting materials were Nyala in Sudan and Mombasa in Kenya. To our knowledge, these are the first scientific records of baobab in Uganda and some research questions and key propositions are formulated based on this discovery.