Neural architecture search (NAS) is a powerful technique that automates neural network design, significantly enhancing model performance. This paper considers NAS for multi-task learning (MTL), in which a single model handles multiple tasks in parallel. The core idea in neural network-based MTL is that models trained on similar tasks share more hidden layers before splitting into task-specific layers, thereby creating a more generalized feature representation that benefits both tasks. While task similarity is crucial for knowledge transfer within transfer learning, its use in MTL is underexplored. We propose MTL-SIMNAS as a novel method that leverages task similarity to constrain the search space by determining the number of shared hidden layers, guiding NAS to optimal MTL architectures. We have thoroughly evaluated MTL-SIMNAS in terms of performance, convergence rate, and complexity reduction against several benchmark methods. Experiments on diverse datasets show that MTL-SIMNAS outperforms the benchmark, reduces complexity, and achieves faster convergence in over 56% of the models.