While creating a new course, you can add a new category, assuming of course that you have the appropriate permissions to do so. 

When adding a new course instead of selecting among the available categories, start typing the name of the new category you want to add your new course to (1). You will get prompted to actually add the new category (2).

After that, the newly added category will be selected for the course category option.

Note: The new category you just added this way will not be permanently stored in your available categories unless you finish the process of adding the new course and submitting the new course form.

Once you have completed the process of adding the new course the new category will be available to edit in your categories list.