Insertions and deletions (InDels) are frequently observed in natural protein evolution, yet their potential remains untapped in laboratory evolution. Here we introduce a transposon mutagenesis approach (TRIAD) to generate libraries of random variants with short in-frame InDels, and screen TRIAD libraries to evolve a promiscuous arylesterase activity in a phosphotriesterase. The evolution exhibits features that are distinct from previous point mutagenesis campaigns: while the average activity of TRIAD variants is more deleterious, a larger proportion has successfully adapted for the new activity, and different functional profiles emerge: (i) both strong and weak trade-off between original vs promiscuous activity are observed; (ii) trade-off is more severe (20- to 35-fold increased kcat/KM in arylesterase with 60-400-fold decreases in the original phosphotriesterase activity) and (iii) improvements show up in kcat rather than just in KM, suggesting novel adaptive solutions. These distinct features make TRIAD an alternative to widely used point mutagenesis, providing access to functional innovations and traversing unexplored fitness landscape regions.