Also, AppArmor might not exist without SELinux.
When the NSA first implemented SELinux, they did so directly, but were not able to get that merged into mainline because there was concern that SELinux was not the correct solution.
What they ended up doing was creating the Linux Security Modules (LSM) framework, which is just a bunch of hooks in the kernel that a module can implement. SELinux was then rewritten as LSM module. This allowed other solutions like AppArmor to be implemented without any invasive work; they could just plug into the same system SELinux used.
Some time later, the ability to run multiple LSMs at once was added.
Incidentally, Linux capabilities are also implemented as an LSM.
If you are building a static system, SELinux is amazing. You need a few lines of policy per application to label things appropriately, then you can see what accesses programs made and decide if you want to allow them or not.
Taking a full Linux system and adding a locked down SELinux policy can be done in less than a week. If you are starting with an SELinux enabled system and just want to lock down your application, it can be done in less than a day.
Once you know what you are doing, there is also a pretty powerful policy analysis tool that lets you see what a given domain can do; including transitive things like “domain sandbox_t can launch a program in Domain vim_t, which can write a file in Domain sshd_config_t, which can be read by domain sshd_t” which may indicate that your sandbox has a hole allowing it to compromise your sshd configuration. Although, to be fair, doing this level of analysis is not simple, even with the tooling. And you very quickly notice issues that are inherent in how Linux works.
The problem with SELinux comes when you try applying it to general purpose systems, because you do not know ahead of time what the user will want to do. To be effective, policy needs to be written for the specific system it will be running on.
An example I like to use is Android. Android makes great use of SELinux, and is a general purpose system. But the SELinux policy itself does not protect the general purpose Android system. It protects the special purpose system that is the Android runtime. All apps run with the same policy that says things like “cannot access the filesystem at all, unless given access by the Android runtime”, then the actual security policy users see is all implemented in use space by Android. SElinux is just a means of preventing apps from bypassing the Android permission system.