Alan Kay claims that "I made up the term "object-oriented", and I can tell you I did not have C++ in mind." What he had in mind, of course, was Smalltalk. But he did not make up object-oriented programming itself; he got the basic ideas from Simula. So if the term hadn't been invented yet, what did they originally call object-oriented programming in Simula?
Actually Alan Kay didn't have Smalltalk in mind when he came up with the term "object oriented programming":
At Utah sometime after Nov 66 when, influenced by Sketchpad, Simula, the design for the ARPAnet, the Burroughs B5000, and my background in Biology and Mathematics, I thought of an architecture for programming. It was probably in 1967 when someone asked me what I was doing, and I said: "It's object-oriented programming".
The original conception of it had the following parts.
- I thought of objects being like biological cells and/or individual computers on a network, only able to communicate with messages (so messaging came at the very beginning -- it took a while to see how to do messaging in a programming language efficiently enough to be useful).
- I wanted to get rid of data. The B5000 almost did this via its almost unbelievable HW architecture. I realized that the cell/whole-computer metaphor would get rid of data, and that "<-" would be just another message token (it took me quite a while to think this out because I really thought of all these symbols as names for functions and procedures.
- My math background made me realize that each object could have several algebras associated with it, and there could be families of these, and that these would be very very useful. The term "polymorphism" was imposed much later (I think by Peter Wegner) and it isn't quite valid, since it really comes from the nomenclature of functions, and I wanted quite a bit more than functions. I made up a term "genericity" for dealing with generic behaviors in a quasi-algebraic form.
- I didn't like the way Simula I or Simula 67 did inheritance (though I thought Nygaard and Dahl were just tremendous thinkers and designers). So I decided to leave out inheritance as a built-in feature until I understood it better.
Smalltalk was the result of this conception, borrowing and extending the concepts of "object" and "class" from Simula, which Simula in turn inherited from ALGOL, as described on "The development of the Simula languages" by Kristen Nygaard and Ole-Johan Dahl (1978, page 253):
In ALGOL, blocks (including procedures) are seen externally as generalized operations. By introducing mechanisms for quasi-parallel sequencing, ~essentially the same construct could play the role of processes in parallel, and through mechanisms for naming block instances and accessing their contents they could function as generalized data objects. The essential benefits of combining data and operations in a single construct were already there to be explored.
One result of this exploration was the discovery that "procedure attributes" might be useful. The following example of a class of "abstract" car objects is quoted from the Language Definition document (Dahl and Nygaard 1965), sect. 5.3.
Further inspiration, especially for sub-classing, was C.A.R. Hoare's record class (page 258):
The subclass idea of Hoare (68) was a natural starting point, but there were two difficulties:
- We needed subclasses of processes with own actions and local data stacks, not only of pure data records.
- We also needed to group together common process properties in such a way that they could be applied later, in a variety of different situations not necessarily known in advance.
Much time was spent during the autumn of 1966 in trying to adapt Hoare's record class construct to meet our requirements, without success. The solution came suddenly, with the idea of "prefixing", in December 1966. We were thinking in terms of atoll booth on a bridge, with a queue of cars which were either trucks or buses. (This example reappears in (Dahl and Nygaard 1968)).
The terms "class" and "object" also appear on SIMULA 67 COMMON BASE LANGUAGE by Ole-Johan Dahl, Bjorm Myhrhaug, and Kristen Nygaard (pages 4-5):
The block concept corresponds to the intuitive notion of "sub-problem" or "sub-algorithm" which is a useful unit of decomposition in orthodox application areas.
A block is a formal description, or "pattern" of an aggregated data structure and and associated algorithms and actions.
An extended block concept is introduced through a "class" declaration and associated interaction mechanism such as "object references" (pointers), remote accessing", "quasi-parallel" operation, and block "concatenation".
Classes are discussed in more detail in chapter 1.3.3 (page 5):
A central new concept in Simula 67 is the "object". An object is a self-contained program (block instance), having its own local data and actions defined by a "class declaration". The class declaration defines a program (data and action) pattern, and objects conforming to that pattern are said to "belong to the same class".
So, although the term "object oriented" wasn't invented yet, both "class" and "object" were used similarly to their modern use before Alan Kay began developing Smalltalk in 1969.
Ivan Sutherland goes as far as identifying Simula as the first object oriented programming language, on Sketchpad: A man-machine graphical communication system (page 4), also recognizing C.A.R. Hoare's, Douglas T. Ross', ALGOL's and Sketchpad's influences:
Nevertheless, Sutherland's attempt to remove the division between users and programmers was not the only system that, in failing to do so, provided the imaginative leap to a new programming paradigm. Nygaard and Dahl's Simula  was the first conventional programming language incorporating the principles of object orientation, but Sketchpad's implementation of class and instance-based inheritance (though not called objects) predated Simula by several years.
There appears to have been a common influence through the work of Douglas T. Ross, who is mentioned in the acknowledgements of this dissertation and also cited in the MIT Lincoln Laboratory technical report based on it. Ross sat on the Algol 68 committee with C. A. R. Hoare in the mid-1960s, where his previous work on a record-like data structure (called a plex) influenced Hoare's own ideas on abstract data types , later credited by Nygaard and Dahl as the origin of the class definition mechanisms in Simula .
Alan Kay's seminal Dynabook project, which led both to the Xerox Star and to the explosion of interest in object oriented programming through his language Smalltalk, was directly influenced by Sketchpad. Kay has written of the fact that the genesis of Smalltalk lay in the coincidental appearance on his desk of both a distribution tape of Simula and a copy of Sutherland's Sketchpad thesis . Kay recognized that the two systems were based on the same underlying type concepts (apparently derived via two different routes from Ross's plex), and that these could form the basis of a more widely usable programming system. In comparing these two routes of influence, Simula was a far larger project than Sketchpad, rightly recognized as the first object-oriented programming language, but we hope that the special emphasis of Sketchpad on supporting abstraction in the user interface itself may yet become viable as a result of ongoing research efforts [2,6].
However Alan Kay, obviously, considers Smalltalk to be the first object oriented language:
Though it has noble ancestors indeed, Smalltalk’s contribution is a new design paradigm–which I called object-oriented–for attacking large problems of the professional programmer, and making small ones possible for the novice user. Object-oriented design is a successful attempt to qualitatively improve the efficiency of modeling the ever more complex dynamic systems and user relationships made possible by the silicon explosion.
and having coined the term, I think there isn't much of a debate there.
To finally answer your question: Some of the core concepts of object orientation did exist on Simula, and on earlier languages like Algol and LISP, but the paradigm itself didn't, hence there wasn't really a need for a name.
Smalltalk was designed with object orientation in mind, at least what Alan Kay thought of as object orientation:
OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them.
The architecture may seem like an amalgamation of earlier concepts, but its central concepts were introduced by Smalltalk, thus marking the first implementation of the paradigm.