Studies in software effort estimation (SEE) have explored the use of machine learning algorithms (MLA) to improve the accuracy of effort estimates. In particular, support vector regression (SVR) has recently shown promising results in this area. However, the accuracy of MLA-based estimations depends on the chosen hyper-parameter settings. To tune these hyper-parameters, many studies have used exhaustive approaches such as grid search (GS). However, in other contexts random search (RS) has shown similar results to grid search, while being less computationally-expensive. In this paper, we investigate to what extent the random search hyper-parameter tuning approach affects the accuracy and stability of SVR in SEE. Results were compared to those obtained from ridge regression models and grid search-tuned models. A case study with four data sets extracted from the ISBSG 2018 repository shows that random search exhibits similar performance to grid search, rendering it an attractive alternative technique for hyper-parameter tuning. RS-tuned SVR achieved an increase of 0.183 standardized accuracy (SA) with respect to default hyper-parameters. In addition, random search improved prediction stability of SVR models to a minimum ratio of 0.707. A Scott-Knott analysis determined that the combination of parameter tuning, logarithmic data transformation, and SVR was the most effective approach in all studied data sets. Moreover, the analysis showed that RS-tuned SVR attained performance equivalent to GS-tuned SVR. Future work includes extending this research to cover other hyper-parameter tuning approaches and machine learning algorithms, as well as using additional data sets.