En las primeras etapas del proyecto, sus integrantes consideraron la posibilidad de distribuir sólo paquetes con código fuente. Cada paquete consistiría en el código fuente principal más un fichero con el parche debianizado; los usuarios habrían de descomprimir el código fuente, aplicar los parches y compilar por sí mismos los binarios. Sin embargo, pronto se dieron cuenta de que era preciso algún planteamiento de distribución binaria. La herramienta de empaquetado más primitiva, escrita por Ian Murdock y llamada dpkg, creaba un paquete en un formato binario específico de Debian, y podía usarse más tarde para desempaquetar e instalar los ficheros del paquete.
Ian Jackson pronto tomó a su cargo el desarrollo de la herramienta de empaquetado, renombrando a la herramienta en sí como dpkg-deb, y escribiendo una interfaz a la que llamó dpkg para facilitar el uso de dpkg-deb y proporcionar las Dependencias y Conflictos del sistema actual de Debian. Los paquetes producidos por estas herramientas tenían una cabecera que listaba la versión de la herramienta que se había usado para crear el paquete y una sección aparte del paquete para un archivo producido con tar, que mediante cierta información de control se separaba de la cabecera.
Aproximadamente por esta época se suscitó un cierto debate entre los miembros del proyecto. Algunos pensaban que el formato específico de Debian creado por dpkg-deb debía abandonarse en favor del formato que producía el programa ar. Después de varias revisiones del formato de fichero y de las correspondientes revisiones de las herramientas de empaquetado, se adoptó el formato ar. El valor fundamental de este cambio es que hace posible que cualquier paquete .deb se desempaquete en cualquier sistema tipo UNIX sin la necesidad de ejecutar un programa que no sea de confianza. En otras palabras: sólo hacen falta herramientas estándar presentes en cualquier sistema UNIX, como ``ar'' y ``tar'', para desempaquetar un paquete binario Debian y examinar su contenido.