We provide evidence of the structural unemployment rate determinants in Colombia between 1984 and 2015. In the first stage, we estimate different measures of this variable including the ones that emerge from the search-theoretic, the Phillips curve and a structural vector autoregressive model. Next, by using a fully modified ordinary least squares cointegration approach, we test the determinants in the Colombian case following the search model guidelines. Accordingly, the main explanations of the structural unemployment rate are the real minimum wage, the real interest rate, a hiring cost indicator, sectoral shifts, non-wage labour costs and some demographic factors such as the proportion of workers with no college education. Finally, we use these variables to estimate a new measure of the structural unemployment rate called the true structural unemployment rate.