El parque está construido en el sitio de 11 casas demolidas a mediados de la década de 1960, cuando el Departamento de Carreteras del Estado de Georgia propuso construir la Interestatal 485 para conectar lo que ahora es Freedom Parkway a través de Virginia-Highland con lo que ahora es Georgia 400 en la Interestatal 85 . El sitio del parque habría sido la salida de Virginia Avenue de la autopista.
La I-485 finalmente fue derrotada y el Departamento de Transporte de Georgia comenzó a vender las propiedades que había adquirido. En 1988, se inauguró el parque.
A principios de la década de 1980, se creó Virginia Highland Civic Fund, Inc. para planificar y desarrollar el espacio. El diseño del parque surgió de un estudio ampliamente distribuido en todo el vecindario. A fines de la década de 1980, el Proyecto Living AIDS Memorial Park y Volleyball Atlanta se unieron al esfuerzo y proporcionaron ayuda técnica y de recaudación de fondos.
En 1989, el parque recibió su nombre en honor al residente de Virginia-Highland y activista contra las autopistas John Howell , quien murió por complicaciones del VIH en 1988.
Peter Frawley & Associates, una firma local de arquitectura paisajista, coordinó todas las aportaciones. En febrero de 1993, el Ayuntamiento de Atlanta aprobó el plan final del parque. El proyecto de construcción y recaudación de fondos de una década fue dirigido por Jerry Bright y Rick Porter. Las minutas corporativas del Proyecto John Howell Park de 1985-2000 y otros documentos históricos están disponibles en la Biblioteca de la Universidad de Emory en Atlanta.
A lo largo de Virginia Avenue hay once columnas de granito, cada una de las cuales lleva la dirección de una de las casas que fueron demolidas.