In this paper, we analyze how a set of slow moving determinants affect trade between the EU on one hand, and CEECs (Central and Eastern European countries) and African countries on the other hand, over the period 2005-2012. We focus on two sets of slow moving determinants, doing business institutions and logistical infrastructure, as well as embassies and ambassadors, by controlling for many other possible time-invariant trade cost determinants. Trade is disentangled for three types of goods: primary goods, parts and components and capital goods. Methodologically, we first derive dyadic country-pair fixed effects and in a second stage we correlate fixed effects with a set of influential factors. In our analysis, (i) we identify the beneficial effects of soft and hard infrastructure; (ii) we compare the latter with the benefit of opening an embassy and also compute the extra trade that would follow a move towards a better score of the trade facilitation and doing business indicators; and (iii) we show that a huge part of the missing bilateral trade fixed effect of North African countries is accounted for by soft and hard infrastructure, and that diplomatic activity is also a powerful driver of regional integration.