This paper presents a new approach to design the architecture and optimize the hyperparameters of a deep convolutional neural network (CNN) via of the Fractal Decomposition Algorithm (FDA). This optimization algorithm was recently proposed to solve continuous optimization problems. It is based on a geometric fractal decomposition that divides the search space while searching for the best solution possible. As FDA is effective in single-objective optimization, in this work we aim to prove that it can also be successfully applied to fine-tuning deep neural network architectures. Moreover, a new formulation based on bi-level optimization is proposed to separate the architecture search composed of discrete parameters from hyperparameters’ optimization. This is motivated by the fact that automating the construction of deep neural architecture has been an important focus over recent years as manual construction is considerably time-consuming, error-prone, and requires in-depth knowledge. To solve the bi-level problem thus formulated, a random search is performed aiming to create a set of candidate architectures. Then, the best ones are finetuned using FDA. CIFAR-10 and CIFAR-100 benchmarks were used to evaluate the performance of the proposed approach. The results obtained are among the state of the art in the corresponding class of networks (low number of parameters and chained-structured CNN architectures). The results are emphasized by the fact that the whole process was performed using low computing power with only 3 NVIDIA V100 GPUs. The source code is available at https://github.com/alc1218/Convolutional-Neural-Network-Architecture-Search-Based-on-Fractal-Decomposition-Optimization.