Velma débute par un album auto-produit Rythmique et des apparitions sur diverses compilations (voir discographie) et des tournées modestes en Suisse et en Europe. En été 1999, le groupe a signé avec le label californien Emperor Norton Records pour l’album Cyclique,. Ce même album est sorti en Europe sur les labels Noise Product et Namskeio Records. D’autre part, Parole un 12-inch présentant les derniers enregistrements du groupe est sorti sur le label Stetic Records (distribué par Namskeio Records) en mars 2000.
Parole a été réédité en format CD sous le titre Panoramique à la fin de l'année 2001 sur M Narsitik Records, avec des remixes de Pluramon (Allemagne), Jan Jelinek (Allemagne), Bruce Gilbert (Angleterre), Alog (Norvège), Terre Thaemlitz (Japon), entre autres.
Produit en juin 2002 par Mark Van Hoen (Locust, Seefeel, Mojave 3, Scala, Annie Williams, Sing-Sing), Ludwig, le troisième album de Velma est le successeur longtemps attendu de Cyclique. Cette collaboration a permis à Velma de développer un son plus pop et plus abouti. La sortie de Ludwig a été suivie de près par un split single avec le groupe de hip-hop new-yorkais Dälek. Ce vinyle est sorti fin 2002. En 2003 est paru un petit 45 tours sur le label français Lykill.
En octobre 2005, sort La pointe Farinet 2'949m., le quatrième album du trio sur deux différents labels : les Français de Monopsone et les Suisses de Gentlemen. Toujours produit par Mark Van Hoen, ce dernier né est cette fois hanté par des boucles hip hop sales et chargées. La pointe Farinet, 2'949 m. est porté par quelques moments intenses comme Metropolis (une reprise de Mötorhead) et Voices Of The Ether en collaboration avec Dälek.
