El Diccionario de la lengua española (DLE) registra que la etimología de malandro proviene del italiano malandro, derivado de malandrino. Según Joan Corominas, en el Diccionario crítico etimológico castellano e hispánico (1984), malandrín procede del italiano malandrino (‘salteador’) o del catalán antiguo malandrí (‘bellaco, rufián’), voces que originalmente significaban «pordiosero leproso». Posteriormente, malandrín adquirió el sentido de ‘salteador, ladrón de caminos’, mientras que malandro se empleó con el significado de ‘maleante’.

El primer registro documentado en castellano data de 1634 en España, en la obra Rimas humanas y divinas del licenciado Tomé de Burguillos de Lope de Vega: «Yo soy Marramaquiz, yo noble al doble de todo gato de ascendiente noble; si tú de Zapirón, yo de Malandro, gato de macedón Magno Alejandro desciendo». En este caso, Malandro se utiliza como nombre propio y no con la acepción actual.

Posteriormente, la palabra reaparece en la literatura venezolana y después en distintos países de América Latina. En Venezuela se registra en 1980 en Cuentos de Gustavo Luis Carrera: «algún día te veré, viejo malandro, sirviendo de mesa en mesa». En este contexto, el término se emplea como apelativo despectivo y se interpreta con el sentido de ‘delincuente’, de acuerdo con lo señalado en diccionarios como el DLE, el Diccionario de americanismos (DA) y el Diccionario de venezolanismos.

En Puerto Rico también se documenta el uso del término con la acepción de ‘delincuente’, como en el ejemplo: «el miedo al asedio de los limosneros, el miedo a sacar la cartera y que me la arrebate ese malandro de mirada omnipresente que no alcancé a ver». En México, la palabra aparece vinculada a la película brasileña Ópera do Malandro (1986), dirigida por Ruy Guerra, cuyo protagonista es un delincuente, conservando así la misma acepción.

Además de la forma masculina, se encuentran registros del femenino malandra en varios países latinoamericanos, siempre con el mismo sentido. En Argentina aparece en textos de Rodolfo Walsh entre 1951 y 1961: «La ley de los jueces siempre termina por enfrentarlo a uno con un malandra que esa noche tiene más suerte, o mejor puntería (…)». En Puerto Rico se registra en 1989 con Edgardo Rodríguez Juliá: «su malevolencia malandra acentuada con varias vueltas de cadenas de oro que le cuelgan por el cuello de luchador (…)». En Uruguay se encuentra en un texto de Eduardo Galeano: «Garrincha ejercía sus picardías de malandra a la orilla de la cancha (…)». En Venezuela también aparece en la obra de Gustavo Luis Carrera: «así la terminología profesional o policial acostumbrada o periodística o usual o malandra o convencional o radiofónica o revolucionaria o militar (…)».

Los usos documentados de malandro y malandra en América Latina muestran un significado estable: ‘persona que comete actos delictivos’. De esta manera, el sentido original registrado en España en 1634 desapareció, y a partir de la segunda mitad del siglo XX se consolidó en países latinoamericanos el valor de ‘delincuente’. Este cambio semántico se ha explicado como resultado de diversos factores lingüísticos, sociales y culturales, incluyendo la influencia extranjera o la necesidad de designar de manera específica a quienes se dedican a actividades delictivas.^[1]​

En Venezuela existe la aféresis «landro» (y su femenino «landra»), que conserva el mismo significado que malandro: «persona de malas costumbres».^[6]​