A natural development of the recent work about semistar operations leads to investigate the concept of "semistar invertibility". Here, we show the existence of a "theoretical obstruction" for extending many results, proved for star-invertibility, to the semistar case. For this reason, we introduce two distinct notions of invertibility in the semistar setting (called *-invertibility and quasi-*-invertibility), we discuss the motivations of these "two levels" of invertibility and we extend, accordingly, many classical results proved for the d-, v-, t- and w-invertibility.