Cyberbullying is a ubiquitous topic when considering young people and internet and communication technologies (ICTs). For interventional purposes, it is essential to take into account the perspective of adolescents. This is the reason why our main focus is (1) investigating the role of different criteria in the perceived severity of cyberbullying incidents, and (2) examining the differences between countries in the perceived severity of cyberbullying. The sample consisted of 1,964 adolescents (48.2% girls) from middle and high schools of four different countries, i.e., Estonia, Italy, Germany, and Turkey. The participants' age ranged from 12 to 20 years old with a mean age of 14.49 (SD = 1.66) years. To assess perceived severity, participants rated a set of 128 scenarios, which systematically included one or more of five criteria (intentionality, repetition, imbalance of power, public vs. private, and anonymity) and represented four types of cyberbullying behaviors (Written—Verbal, Visual, Exclusion, Impersonation). The role of different criteria was analyzed using the Exploratory Structural Equation Modeling (ESEM). Results showed a similar structure across the four countries (invariant except for the latent factors' means). Further, criteria of imbalance of power and, to a lesser extent, intentionality, anonymity, and repetition always in combination, were found to be the most important criteria to define the severity of cyberbullying. Differences between countries highlighted specific features of Turkish students, who perceived all scenarios as more severe than adolescents from other countries and were more sensitive to imbalance of power. German and Italian students showed an opposite perception of anonymity combined with intentionality. For Italian participants, an anonymous attack was less threatening than for participants of other countries, whereas for German students anonymity caused more insecurity and fear. In addition, Italian adolescents were more perceptive of the criterion of intentionality. Finally, Estonian adolescents did not show strong differences in their factor scores compared to adolescents from the other countries.