En 1968 el Ayuntamiento de Benalmádena llega al compromiso con Felipe Orlando de construir un edificio de nueva planta para albergar la colección donada por él y exponerla al público, este edificio se inauguró el 5 de mayo de 1970. El Museo se sitúa en la avenida principal del pueblo, sobre un solar de unos 203,97 m2 perteneciente a unos antiguos terrenos del obispado.

El proyecto del museo es del arquitecto Antonio Luque Navajas, quien concibió un edificio con la apariencia de una casa señorial y que contrasta con la tipología de viviendas habituales de su entorno inmediato. Este carácter noble, que se refleja sobre toda la fachada, venía determinado por su acceso, consistente en una entrada adintelada de piedra artificial a la que precede una amplia escalinata que salva el desnivel del terreno y que dota al edificio de una mayor perspectiva visual, carácter este que se mantendrá tras la última intervención. La fachada presentaba cuatro vanos que terminaban en una suerte de frontal de perfiles irregulares en la parte central. 

El 27 de abril de 2005 el Museo abrió de nuevo sus puertas tras una ambiciosa reforma, que ha posibilitado que el recinto esté totalmente adaptado a las exigencias de la nueva museología, con un nuevo montaje de su exposición y un diseño funcional y moderno

Este proyecto, realizado entre el 2003 y 2005 por el arquitecto Raúl Gantes Rodríguez, afectan tanto a la fachada como al interior del edificio. Así, los grandes vanos o ventanas enrejadas primitivas de la fachada, que flanqueaban la entrada en la primera planta y cuyo aspecto acentuaba el carácter de casa popular andaluza, han sido suprimidos y sustituidos por cierres de cristal. El enfático frontón que la remataba ha sido igualmente eliminado, contribuyendo con ello a ofrecer una imagen más sobria pero también más moderna y acorde con las funciones museológicas del edificio. De los vanos pequeños de la segunda planta sólo se conserva el del lado derecho, ocultándose el izquierdo que ha sido sustituido por la cartela anunciadora de la institución. Frente al edificio, permanece el simbólico y bello ciprés que se erige como perpetuo vigía y símbolo de perennidad.

Las tres plantas interiores han sido objeto de profundas reformas, una intervención que ha añadido 200 m2 de superficie. Siguiendo un criterio de funcionalidad, el arquitecto ha diseñado con acierto diferentes espacios plenos de luz y de eficaz circulación, con cuatro lucernarios en la planta alta y amplios ventanales en la planta principal, que proporcionan luz natural a las respectivas salas. La cubierta de teja respeta y contextualiza el contorno de los edificios colindantes.

Como todo museo correctamente planteado, el Museo Precolombino de Benalmádena sigue, desde su remodelación y reapertura en 2005, estrictos criterios museológicos y museográficos, respondiendo los primeros a la experiencia y buen hacer de Paz Cabello, actual directora del Museo de América de Madrid, y artífice a su vez de la catalogación de la Colección Precolombina, para lo cual su autora ha realizado un guion expositivo encaminado a mostrar las piezas de la forma más didáctica y clarificadora.
Los espacios de la primera planta, dedicada fundamentalmente a México, y la segunda, que centra su atención mayoritariamente en Perú, Ecuador, Nicaragua y Colombia, presentan un concepto más temático que de organización por culturas, ofreciendo una secuencia óptima de lo que han significado las distintas regiones Mesoamericanas y Andinas a través de piezas representativas de ellas.

La planta baja está dedicada a la colección arqueológica hispánica, cuyo guion museológico ha sido diseñado por el arqueólogo Gonzalo Pineda de las Infantas Beato, mostrando los restos conservados de las distintas culturas asentadas en el municipio.

Este nivel alberga también la exposición de pintura de Felipe Orlando, así como almacenes y talleres.